class Binarytree:
def __init__(self, node):
"""
:param node: root node
"""
self.node = node
self.left = None
self.right = None
def add_node(self, node):
"""
:param node: append node
:return: None
"""
if node == self.node:
return
if node < self.node:
if self.left:
self.left.add_node(node)
else:
self.left = Binarytree(node)
else:
if self.right:
self.right.add_node(node)
else:
self.right = Binarytree(node)
def search(self, val):
"""
:param val: value to search in binary tree
:return: True if found else False
"""
if val == self.node:
return True
if val < self.node:
if self.left:
return self.left.search(val)
else:
return False
else:
if self.right:
return self.right.search(val)
else:
return False
def print_nodes(self):
"""
print all node values to console window
:return: None
"""
if self.left:
self.left.print_nodes()
print(self.node)
if self.right:
self.right.print_nodes()
return False
def build_tree(node):
"""
:param node: list of nodes
:return: Binarytree with nodes
"""
root = Binarytree(node[0])
for i in range(1, len(node)):
root.add_node(node[i])
return root
if __name__ == '__main__':
nodes = [30, 10, 40, 22, 15, 18]
tree = build_tree(nodes)
tree.add_node(18)
tree.add_node(20)
print("15 found in binary tree", tree.search(15))
print("100 found in binary tree", tree.search(100))
tree.print_nodes()
"""Binary Search Tree
Included:
- Insert
- Find data/ minimum/ maximum
- Size
- Height
- Traversals (Inorder, preorder, postorder)
- Test Code for it
Not included:
- Delete
- Display (as 2D BST)
and others...
"""
class Node: # Node
def __init__(self, data, start=None):
self.data = data
self.left = self.right = start
class BinarySearchTree:
def __init__(self):
self.root = None
# Insert a node
def put(self, data):
if self.root is None: # BST empty
self.root = Node(data)
else:
curr = self.root # initialise curr pointer
while curr:
if data < curr.data: # data put at left
if curr.left:
curr = curr.left
else: # no left child
curr.left = Node(data)
break
else: # data put at right
if curr.right:
curr = curr.right
else: # no right child
curr.right = Node(data)
break
def find(self, data):
curr = self.root # start from root
while curr:
if data < curr.data: # data at left
curr = curr.left
elif data > curr.data: # data at right
curr = curr.right
else:
return True # found
return False
def min_of(self):
curr = self.root # start from root
while curr.left:
curr = curr.left # keep going left
return curr.data
def max_of(self):
curr = self.root # start from root
while curr.right:
curr = curr.right # keep going right
return curr.data
def size(self):
def go(node): # helper
if node:
return 1 + go(node.left) + go(node.right)
return 0
return go(self.root)
def height(self):
def go(node): # helper
if node:
return 1 + max(go(node.left), go(node.right))
return -1 # it has -1 if empty
return go(self.root)
# In_order
def in_order(self):
lst = [] # results
def go(node): # helper
nonlocal lst
if node: # If node exists
go(node.left) # left
lst.append(node.data) # Node
go(node.right) # Right
go(self.root)
return lst
# Pre_order
def pre_order(self):
lst = [] # results
def go(node): # helper
nonlocal lst
if node: # If node exists
lst.append(node.data) # Node
go(node.left) # left
go(node.right) # Right
go(self.root)
return lst
# Post_order
def post_order(self):
lst = [] # results
def go(node): # helper
nonlocal lst
if node: # If node exists
go(node.left) # left
go(node.right) # Right
lst.append(node.data) # Node
go(self.root)
return lst
# Test
from random import randint, sample
def BST_tester(BST):
r = randint(5, 10)
lst = [randint(10, 100) for _ in range(r)]
print(f"List: {lst}",
f"Sorted: {sorted(lst)}",
sep = "\n", end = "\n\n")
B = BST()
for item in lst:
B.put(item)
lst.sort()
print("AFTER INSERTION:",
f"Size: {B.size()} | {B.size() == len(lst)}",
f"Height: {B.height()} | I can't code the display for this",
f"Min: {B.min_()} | {B.min_() == min(lst)}",
f"Max: {B.max_()} | {B.max_() == max(lst)}",
sep = "\n", end = "\n\n")
items = sample(lst, 5) + [randint(10, 100) for _ in range(5)] # 5 confirm in list, 5 might be in list
found = [B.find(_) for _ in items]
zipped = list(zip(items, found))
inlst, notinlst = zipped[:5], zipped[5:]
print(f"Sampled from lst: {inlst} | All True: {all(found[:5])}",
f"Random: {notinlst}",
sep = "\n", end = "\n\n")
print(f"Inord: {B.in_ord()} | Correct Insertion: {lst == B.in_ord()}",
f"Preord: {B.pre_ord()}",
f"Postord: {B.post_ord()}",
sep = "\n")
BST_tester(BST)# বাইনারি সার্চ ট্রি-এর ক্ষেত্রে ২ টি বিষয় মাথায় রাখতে হবে:
'''
১. যদি ট্রি-তে আগে থেকে কোনো নোড না থাকে (অর্থাৎ বর্তমান root নোড none থাকবে),
তাহলে নতুন যোগ করা নোডটিই হবে ট্রি- এর root নোড । আবার-
২. নতুন নোডটি যদি root নোডের সরাসরি চাইল্ড হয়, তাহলেও root নোডের পরিবর্তন ঘটবে।
এ কারণেই আমরা root নোডকে রিটার্ন করি।
'''
# There are two things to keep in mind when it comes to binary search trees:
'''
1. If the tree does not already have a node (ie the existing root node will have none),
then the newly added node will be the root node of the tree. Again
2. If the new node is a direct child of the root node, the root node will also change.
This is why we return to the root node.
'''
# 1st system:
class TreeNode:
def __init__(self,data):
self.data = data
self.parent = None
self.left = None
self.right = None
def __repr__(self):
return repr(self.data)
def add_left(self, node):
self.left = node
if node is not None:
node.parent = self
def add_right(self, node):
self.right = node
node.parent = self
# now bst_insert:
def bst_insert(root,node):
last_node = None
current_node = root
while current_node is not None:
last_node = current_node
if node.data < current_node.data:
current_node = current_node.left
else:
current_node = current_node.right
if last_node is None:
# tree was empty. node is the only node, hence root
root = node # new node add
elif node.data < last_node.data:
last_node.add_left(node)
else:
last_node.add_right(node)
return root
'''
_10_
/ \
5 17
/ / \
3 12 19
/ \
1 4
'''
# now create_bst:
def create_bst():
li = list(map(int,input().split()))
root = TreeNode(li)
for item in root:
node = TreeNode(item)
root = bst_insert(root, node)
return root
# In_order tree traverse:
def in_order(node):
if node.left:
in_order(node.left)
print(node)
if node.right:
in_order(node.right)
# bst- tree minimum node:
def bst_minimum(root):
while root.left is not None:
root = root.left
print(root)
# bst_tree maximum node:
def bst_maximum(root):
while root.right is not None:
root = root.right
print(root)
# এখন আমরা BST-তে কোনো ডেটা খুঁজে বের করার ফাংশন টি লিখে ফেলি।
# Now we write the function to find any data in BST.
def best_search(node,key):
while node is not None:
if node.data == key:
return node
if key < node.data:
node = node.left
else:
node = node.right
return node
# Now check to your code:
if __name__ == "__main__":
root = create_bst()
print("Tree is root =",root)
print()
# In_order tree traverse:
print("In_order Tree:")
in_order(root)
print()
# bst- tree minimum node:
print("Minimum node:")
bst_minimum(root)
print()
# bst_tree maximum node:
print("Maximum node:")
bst_maximum(root)
print()
# input with searching:
print("bst_search:")
for key in [int(input("Please Enter the search key: ")),int(input("Please Enter the search key: "))]:
print("Searching =",key)
result = best_search(root, key)
print("Result =",result)
# বাইনারি সার্চ ট্রি-এর ক্ষেত্রে ২ টি বিষয় মাথায় রাখতে হবে:
'''
১. যদি ট্রি-তে আগে থেকে কোনো নোড না থাকে (অর্থাৎ বর্তমান root নোড none থাকবে),
তাহলে নতুন যোগ করা নোডটিই হবে ট্রি- এর root নোড । আবার-
২. নতুন নোডটি যদি root নোডের সরাসরি চাইল্ড হয়, তাহলেও root নোডের পরিবর্তন ঘটবে।
এ কারণেই আমরা root নোডকে রিটার্ন করি।
'''
# There are two things to keep in mind when it comes to binary search trees:
'''
1. If the tree does not already have a node (ie the existing root node will have none),
then the newly added node will be the root node of the tree. Again
2. If the new node is a direct child of the root node, the root node will also change.
This is why we return to the root node.
'''
# second system:
class TreeNode:
def __init__(self,data):
self.data = data
self.parent = None
self.left = None
self.right = None
def __repr__(self):
return repr(self.data)
def add_left(self, node):
self.left = node
if node is not None:
node.parent = self
def add_right(self, node):
self.right = node
node.parent = self
# now bst_insert:
def bst_insert(root,node):
last_node = None
current_node = root
while current_node is not None:
last_node = current_node
if node.data < current_node.data:
current_node = current_node.left
else:
current_node = current_node.right
if last_node is None:
# tree was empty. node is the only node, hence root
root = node # new node add
elif node.data < last_node.data:
last_node.add_left(node)
else:
last_node.add_right(node)
return root
'''
_10_
/ \
5 17
/ / \
3 12 19
/ \
1 4
'''
# now create_bst:
def create_bst():
root = TreeNode(10)
for item in [5,17,3,7,12,19,1,4]:
node = TreeNode(item)
root = bst_insert(root, node)
return root
# In_order tree traverse:
def in_order(node):
if node.left:
in_order(node.left)
print(node)
if node.right:
in_order(node.right)
# bst- tree minimum node:
def bst_minimum(root):
while root.left is not None:
root = root.left
print(root)
# Node transfer:
def bst_transfer(root, current_node, new_node):
if current_node.parent is None:
root = new_node
elif current_node == current_node.parent.left:
current_node.parent.add_left(new_node)
else:
current_node.parent.add_right(new_node)
return root
# Node delete:
def bst_delete(root,node):
if node.left is None:
root = bst_transfer(root,node,node.right)
elif node.right is None:
root = bst_transfer(root,node,node.left)
else:
min_node = bst_minimum(node.right)
if min_node.parent != node:
root = bst_transfer(root,min_node,min_node.right)
min_node.add_right(node.right)
root = bst_transfer(root,node,min_node)
min_node.add_left(node.left)
return root
# এখন আমরা BST-তে কোনো ডেটা খুঁজে বের করার ফাংশন টি লিখে ফেলি।
# Now we write the function to find any data in BST.
def best_search(node,key):
while node is not None:
if node.data == key:
return node
if key < node.data:
node = node.left
else:
node = node.right
return node
# Now check to your code:
if __name__ == "__main__":
root = create_bst()
print("Tree is root =",root)
print()
print("BST:")
in_order(root)
for key in [1,5,10]:
node = best_search(root,key)
print("will delete =", node)
root = bst_delete(root,node)
print("BST:")
in_order(root)